package array

import "fmt"

func SearchMatrix(matrix [][]int, target int) bool {
	if matrix == nil {
		return false
	}

	var n int
	if len(matrix) < len(matrix[0]) {
		n = len(matrix)
	} else {
		n = len(matrix[0])
	}

	for i := 0; i < n; i++ {
		fmt.Println("======", i, "======")
		row := binarySearch(matrix, target, i, false)
		col := binarySearch(matrix, target, i, true)

		fmt.Println("row:", row)
		fmt.Println("col:", col)
		if row || col {
			return true
		}
	}

	return false

}

func binarySearch(matrix [][]int, target int, start int, vertical bool) bool {

	var first, last int

	if vertical {
		first = start
		last = len(matrix) - 1
	} else {
		first = start
		last = len(matrix[0]) - 1
	}

	for first <= last {
		var mid int
		var temp int
		mid = (first + last) / 2
		if vertical {
			temp = matrix[mid][start]
		} else {
			temp = matrix[start][mid]
		}
		if temp > target {
			last = mid - 1
		} else if temp < target {
			first = mid + 1
		} else {
			return true
		}
		fmt.Println(first, last, temp)
	}

	return false

}

func SearchMatrix2(matrix [][]int, target int) bool {
	var x, y int
	y = 0
	x = len(matrix) - 1

	for x >= 0 && y < len(matrix[0]) {
		var temp int
		temp = matrix[x][y]

		if temp < target {
			y++
		} else if temp > target {
			x--
		} else {
			return true
		}
	}

	return false
}
